One kind of function performed in programmable logic devices is arithmetic. A device such as a configurable logic array of Xilinx, Inc., assignee of the present invention, can perform arithmetic as well as a multitude of other logic functions. Such devices are described in U.S. Pat. Nos. 4,870,302 and 4,706,216, and U.S. patent application Ser. No. 07/387,566, which are incorporated herein by reference. Because these devices are intended for general purpose functions, arithmetic is relatively slow and requires a significant amount of silicon area.
Other programmable logic devices, such as the programmable array logic device described in U.S. Pat. No. 4,124,899 and user programmable devices described in U.S. Pat. No. 4,758,745 also can be programmed to perform arithmetic. These two patents ale also incorporated by reference. In these devices the speed of performing arithmetic and other functions which use carry logic is limited by propagation of the carry signal, and the general purpose logic used to implement the carry function is significant.
For understanding how logic devices perform arithmetic, and particularly what causes delay, the following discussion of arithmetic functions will focus on adders. However, the discussion can easily be extended to apply to subtractors, incrementers, decrementers, and accumulators, in addition to other circuits which use a carry-logic.
The following discussion will focus on operation of the middle stages in a multi-bit adder. The least significant bit is a special case because there can be no carry signal to be received from a less significant bit.
The most significant bit is a special case because the carry bit can be used for determining an overflow condition. These two special cases will be discussed in detail later.
By reference to FIGS. 1a, 1b and 2, it will be explained how the speed of a single bit ripple carry adder (FIGS. 1a and 1b), and thus a multi-bit ripple carry adder constructed by cascading single bit adders (FIG. 2) is constrained by the speed at which the signal at the carry-in terminal is propagated to the carry-out terminal.
The Boolean logic equations governing the behavior of the single bit adder shown in FIG. 1a are: EQU S.sub.i =(A.sub.i .sym.B.sub.i).sym.C.sub.i-1 ( 1) EQU C.sub.i =A.sub.i .multidot.B.sub.i +(A.sub.i .sym.B.sub.i).multidot.C.sub.i-1 ( 2)
where
.sym. represents the exclusive-or (XOR) function, PA1 .multidot. represents the AND function, and PA1 + represents the OR function.
Eq.(1) shows that the sum is a function of a carry-in from a less significant bit in addition to the single bits A.sub.i and B.sub.i being added. The ripple carry adder algorithm of Eqs. (1) and (2) shows that the sum for a particular bit cannot be calculated until the carry-out from the previous bit is available. The sum S.sub.i is the output of an XOR gate and cannot be generated until each of its inputs, one of which is the carry-in signal C.sub.1-1, is available.
Furthermore, the carry-out C.sub.i also cannot be generated until the less significant carry bit C.sub.1-1 is available. Referring now to FIG. 2, the propagation of the carry signal through successive stages of a ripple carry adder will be explained. AND gate 67 in the second adder stage Add.sub.i+1 receives one of its inputs from the output of XOR gate 66 after only 1 gate delay. However, assuming that the carry-in signal C.sub.i-1 is preset (that is, that Add.sub.i is the least significant bit), AND gate 67 could wait an additional 3 gate delays for the effect of A.sub.i and B.sub.i to propagate through gates 61, 62 and 65 before its other input, the carry-out C.sub.i from the less significant bit, has been generated from the carry out of the less significant bit C.sub.i-1 and the less significant bits A.sub.i and B.sub.i to be added. Furthermore, the carry-out C.sub.i+1 of the second bit Add.sub.i+1 is further delayed through 2 more gates after the carry bit C.sub.i has been generated. That is, combining the inputs on A.sub.i+1 and B.sub.i+1 with the carry in signal C.sub.i to generate C.sub.i+1 requires that C.sub.i propagate through AND gate 67 and OR gate 70. Thus, there will not be a valid carry-in signal C.sub.i+1 for input to a third stage until 5 gate delays after the application of the input signals A.sub.i and B.sub.i. Thus, the speed of the conventional ripple carry adder is constrained by the speed of propagation of the carry signal. The propagation delay of a conventional ripple carry adder is 2n+1, gates where n is the number of stages in the multi-bit adder.
Since addition is the foundation of many other important functions and operations, it has been important to the computer industry to devise faster adder circuits by speeding up the carry propagation time. In general, these methods work by trading component density and complexity for carry propagation speed.
One well-known algorithm which achieves a faster carry propagation speed is called look-ahead carry logic. A circuit for implementing look-ahead carry logic is shown in FIG. 3. Understanding this logic requires the introduction of two new variables: EQU P.sub.i =A.sub.i .sym.B.sub.i ( 3) EQU G.sub.i =A.sub.i .multidot.B.sub.i ( 4)
The variable P is called "carry propagate" because when P is high, carry-in is propagated to carry-out. The variable G is called "carry generate" because when G is high, a carry-out is generated by the bits being added.
Eqs.(1) and (2) can be rewritten in terms of these new variables: EQU S.sub.i =P.sub.i .sym.C.sub.i-1 ( 5) EQU C.sub.i =G.sub.i +P.sub.i .multidot.C.sub.i-1 ( 6)
With some minor algebraic manipulation, Eq.(6) can be used to write new equations where the carry bit at each level is dependent only on the addends at each level and the least significant carry bit. The following equations are implemented in the four bit adder shown in FIG. 3: EQU (a) C.sub.0 =A.sub.0 B.sub.0 =G.sub.0 EQU (b) C.sub.1 =G.sub.1 +P.sub.1 C.sub.0 =G.sub.1 +P.sub.1 C.sub.0 EQU (c) C.sub.2 =G.sub.2 +P.sub.2 C.sub.1 =G.sub.2 +P.sub.2 (G.sub.1 +P.sub.1 C.sub.0)=G.sub.2 +P.sub.2 G.sub.1 +P.sub.2 P.sub.1 C.sub.0 EQU (d) C.sub.3 =G.sub.3 +P.sub.3 C.sub.2 =G.sub.3 +P.sub.3 (G.sub.2 +P.sub.2 G.sub.1 +P.sub.2 P.sub.1 C.sub.0 =G.sub.3 +P.sub.3 G.sub.2 +P.sub.3 P.sub.2 G.sub.1 +P.sub.3 P.sub.2 P.sub.1 C.sub.0 ( 7)
Each G.sub.i and Pi is a function only of A.sub.i and B.sub.i and not of previous carry values, as can be seen in Eqs. 3 and 4. Second, note in Eq. 7b that C.sub.1 is calculated as a function of G.sub.1, P.sub.1, and C.sub.0, and that in Eq. 7c, C.sub.2 is calculated as a function of G.sub.2, P.sub.2 and C.sub.1. But since C.sub.1 has been solved in terms of C.sub.0, C.sub.2 can also be solved in terms of C.sub.0. Attention to Eq. 7d, and the more general Eq. 6 will reveal that each C.sub.i is a function of several G.sub.i 's, P.sub.i 's, and C.sub.0. As can be seen in FIG. 3, the less significant bit is fed into the next significant bit only for the calculation of the sum, not for the calculation of the carry bit. Since each carry bit is a function of several G.sub. i 's, P.sub.i 's, and C.sub.0, each carry bit is not dependent on the carry-out of any but the least significant bit. Thus the carry propagation delay of the look-ahead carry circuit is independent of the number of bits being added.
Referring still to FIG. 3 and FIG. 1a, the delay from the application of the input signals (A's and B's) to the appearance of a valid signal at the generate outputs (G.sub.i 's) and propagate outputs (P.sub.i 's) of an adder stage is 1 gate (this can be discerned from FIG. 1a). The delay added in FIG. 3 by the carry restorer portion of the look ahead carry circuitry is 2 gates, which makes a total of a 3 gate delay from the application of the input signals to the adder until the last carry out bit is available. This relationship is independent of the number of bits being added. For a multi-bit adder circuit, the delay will be significantly less than the delay of a conventional ripple carry adder circuit. However, as the number of stages is increased, the number of components increases significantly. Look ahead carry logic requires many more components than the conventional ripple carry adder requires to implement a stage of a multi-bit adder. This illustrates the idea that faster carry-propagation requires higher component density.
FIG. 4 shows another example of circuit components for implementing an adder. The adder of FIG. 4 is very fast, but, like the adder of FIG. 3, uses many components. Again, a faster carry logic requires a higher component density.
Pages 6-30 through 6-44 of Xilinx, Inc., "The Programmable Gate Array Data Book," copyright 1989, and available from Xilinx, Inc., 2100 Logic Drive, San Jose, Calif. 95124, show a variety of adders and counters which can be implemented in prior art Xilinx programmable logic devices. These pages of the Xilinx data book are incorporated herein by reference. Xilinx, Inc., owner of the copyright, has no objection to copying these pages but otherwise reserves all copyright rights whatsoever. The adder of FIG. 4 is shown on page 6-30 of the Xilinx data book. FIG. 5 shows a counter, also shown on page 6-34 of the Xilinx data book. In prior art Xilinx devices, calculating the sum requires one function generator, and calculating the carry function requires another function generator. Typically, two function generators are incorporated in one logic block of a Xilinx prior art configurable logic array.
Thus, in the adder circuits of both FIG. 4 and FIG. 5, and for other Xilinx prior art adder circuits as well, approximately one logic block is required for implementing each stage of an adder or counter.